#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bwt.h"
#include "mtf.h"
#include "../myTypes.h"


typedef  struct{
	int		i;		//indice du première caractère de la rotation
	int		num;	//numéro de ligne dans la matrice
}bwtline_t;


static bwtline_t * mat;	//matrice des décalages
static int		* prec;	//nombre d'occurence de i le précédent
static byte		* data=NULL;
static size_t	buflen;


//-----------------------------------------------------------------------------
void BWT_init(size_t maxbuflen)
//-----------------------------------------------------------------------------
{
	buflen	= maxbuflen;
	mat		= (bwtline_t *)malloc(sizeof(bwtline_t)*buflen);
	prec	= (int *)malloc(sizeof(int)*buflen);
}


//-----------------------------------------------------------------------------
void BWT_freeMem()
//-----------------------------------------------------------------------------
{
	free(mat);
	free(prec);
}


// Partitionnement dans quicksort
//-----------------------------------------------------------------------------
static int part(bwtline_t * mat, int height, int width)
//-----------------------------------------------------------------------------
//place le pivot et retourne son indice
{
	int pivot=0,i=1,j=height-1,k,l,cpt=1;
	bwtline_t swp;

	while(i<j)
	{
		if( data[mat[i].i] > data[mat[0].i] )
		{
			//printf("échanger %d %d\n",i, j);
			//échanger i et j
			swp=mat[i]; mat[i]=mat[j]; mat[j]=swp;
			j--;
		} else if( data[mat[i].i] < data[mat[0].i] ) {
			i++;
		}else{ //egalitée -> chercher le premier caratère différents
			//printf("égalitée\n");
			cpt=1;
			k=mat[i].i;
			l=mat[0].i;
			while( cpt<width)
			{
				k= (k+1)%buflen;
				l= (l+1)%buflen;
				cpt++;
				if(data[k] > data[l] )
				{
					//printf("  échanger %d %d\n",i, j);
					//échanger i et j
					swp=mat[i]; mat[i]=mat[j]; mat[j]=swp;
					j--;
					break;
				}else if( data[k] < data[l] ){
					i++;
					break;
				}
			}
			if(cpt>=width){i++; break;}	//si 2 chaines sont identiques alors toute les chaine son identiques
		}
	}
	if( data[mat[i].i] > data[mat[0].i] )
	{
		pivot = i-1;
	} else if( data[mat[i].i] < data[mat[0].i] ) {
		pivot = i;
	}else{ //egalitée -> chercher le premier caratère différents
		//printf("égalitée finale\n");
		cpt=1;
		k=(mat[i].i+1)%buflen;
		l=(mat[0].i+1)%buflen;

		while( cpt<width )
		{
			if(data[k] > data[l] )
			{
				pivot=i-1;
				break;
			}else if( data[k] < data[l] ){
				pivot=i;
				break;
			}
			k= (k+1)%buflen;
			l= (l+1)%buflen;
			cpt++;
		}
		if(cpt>=width)pivot=i;	//les deux chaines sont identique encore plus VRAIMENT pas de bol :D !!!!
	}
	//printf("placer pivot %d %d\n",0, pivot);
	//mettre le pivot à sa place
	swp=mat[0]; mat[0]=mat[pivot]; mat[pivot]=swp;

	return pivot;
}


//-----------------------------------------------------------------------------
static void pseudoQuickSort(bwtline_t * mat, int height, int width)
//-----------------------------------------------------------------------------
{
	int p;

	if(height>1)
	{
		//printf("initial :"); for(i=0; i<len; i++) printf(" %c",tab[i].val); printf("\n");
		p=part(mat,height,width);
		//printf("p = %d après part :",p); for(i=0; i<len; i++) printf(" %c",tab[i].val); printf("\n");
		pseudoQuickSort(mat,p,width);
		pseudoQuickSort(mat+p+1,height-(p+1),width);
	}
}


//-----------------------------------------------------------------------------
void BWT_encode(bitbuf_t * dst, bitbuf_t * src)
//-----------------------------------------------------------------------------
{
	int i;
	bloc_t	firstline=0;

	data	= src->data;
	buflen	= src->len/8;

	//initialisation de la matrice (F ... L)
	for(i=0; i<buflen; i++)
	{
		mat[i].i	=(buflen-i)%buflen;
		mat[i].num	= i;
		//printf("%d | ",i);
		//for(j=0; j<buflen; j++) printf("%c",data[(mat[i].i+j)%buflen]);
		//printf(" |\n");
	}
	//printf("\n");

	//tris de F
	pseudoQuickSort(mat,buflen,buflen);

	//écriture de L
	for(i=0; i<buflen; i++)
	{
		if( mat[i].num == 0) firstline = i;
		dst->data[i+2] = src->data[(mat[i].i+buflen-1)%buflen];
		//printf("%c",src->data[(mat[i].i+buflen-1)%buflen]);
	}
	//printf("\ni=%d\n",firstline);

	//indice de la première ligne dans F
	bit_write(dst,firstline,16);
	bit_seek(dst,0,0,BITSEEK_SET);
	dst->len = (buflen+2)*8;

	//for(i=0; i<buflen+2; i++) printf("%d ",dst->data[i]);

	//Move to front
	MTF_init();
	MTF_encode(dst, dst);
}


//-----------------------------------------------------------------------------
void BWT_decode(bitbuf_t * dst, bitbuf_t * src)
//-----------------------------------------------------------------------------
{
	int i,j,sum=0;
	int count[256];
	bloc_t firstrow=0;

	MTF_init();
	MTF_decode(src,src);

	firstrow = bit_read(src,16);

	buflen =  (src->len/8)-2;
	data = &src->data[2];

	memset(count,0,256*sizeof(int));

	//Calcul des précédents de i
	for (i = 0; i < buflen; i++)
	{
		prec[i] = count[data[i]];
		count[data[i]]++;
	}
	//for(i=0x61; i<0x61+26; i++) printf("%c=%d ",i,count[i]);fflush(stdout);

	//Calcul des précédents lexicographiquement inférieur à i
	sum = 0;
	for(i = 0; i <256; i++)
	{
		j = count[i];
		count[i] = sum;
		sum += j;
	}

	//reconstruction du message original
	i = firstrow;
	for(j = buflen - 1; j >= 0; j--)
	{
		dst->data[j] = data[i];
		i = prec[i] + count[data[i]];
	}

	dst->len=buflen*8;
}


//-----------------------------------------------------------------------------
void BWT_fileEncode(FILE * out, FILE * in)
//-----------------------------------------------------------------------------
{
	//fonction d'encodage d'un fichier

	bitbuf_t src,dst;

	int bufLen = 8192;

	//initialisation des buffers
	bit_initBuf(&src,bufLen*8);
	bit_initBuf(&dst,(bufLen+2)*8);

	BWT_init(bufLen);

	while(!feof(in)){
		int len=0;

		len=fread(src.data, 1, bufLen, in);

		src.len=8*len;	//1octet = 8bits

		bit_seek(&src,0,0,BITSEEK_SET);
		bit_seek(&dst,0,0,BITSEEK_SET);

		BWT_encode(&dst,&src);

		fwrite(dst.data,(dst.len)/8,1,out);
	}

	BWT_freeMem();
}


//-----------------------------------------------------------------------------
void BWT_fileDecode(FILE * out, FILE * in)
//-----------------------------------------------------------------------------
{
	//fonction de décodage d'un fichier
	bitbuf_t src,dst;
	int bufLen = 8192;

	//initialisation des buffers
	bit_initBuf(&src,(bufLen+2)*8);
	bit_initBuf(&dst,bufLen*8);

	BWT_init(bufLen);

	while( !feof(in) )
	{
		int len = fread(src.data, 1, bufLen+2, in);
		src.len=8*len;
		bit_seek(&src,0,0,BITSEEK_SET);
		bit_seek(&dst,0,0,BITSEEK_SET);

		BWT_decode(&dst,&src);

		fwrite(dst.data, dst.len/8 , 1, out);
	}
	BWT_freeMem();
}


/*
#define NB 	13
int main()
{
	int i;
	bitbuf_t src,dst;

	bit_initBuf(&src,8*NB);
	bit_initBuf(&dst,8*(NB+2));

	src.data[0]='b';
	src.data[1]='a';
	src.data[2]='b';
	src.data[3]='a';
	src.data[4]='r';
	src.data[5]=' ';
	src.data[6]='i';
	src.data[7]='s';
	src.data[8]=' ';
	src.data[9]='b';
	src.data[10]='a';
	src.data[11]='c';
	src.data[12]='k';

	BWT_init(NB);
	BWT_encode(&dst,&src);
	for(i=0; i<NB; i++) src.data[i]='x';
	printf("\n");
	for(i=0; i<buflen+2; i++) printf("%d ",dst.data[i]);
	printf("\n");
	BWT_decode(&src,&dst);

	for(i=0; i<NB; i++) printf("%c",src.curs[i]);
	printf("\n");

	return 0;
}
 */

//
